package labuladong.第四章;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 接雨水
 */
public class ReviceRain {
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap3(arr));
    }

    public static int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        for(int i=1; i<n; i++) {
            int l_max = 0, r_max = 0;
            for(int j=i; j<n; j++){
                r_max = Math.max(r_max, height[j]);
            }
            for(int j=i; j>=0; j--) {
                l_max = Math.max(l_max, height[j]);
            }
            ans = ans + Math.min(r_max, l_max) - height[i];
        }
        return ans;
    }

    public static int trap2(int[] height) {
        int n = height.length;
        int ans = 0;
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        l_max[0] = 0;
        r_max[n-1] = 0;
        for(int i=1; i<n; i++) {
            l_max[i] = Math.max(l_max[i-1], height[i]);
        }
        for(int i=n-2; i>=0; i--) {
            r_max[i] = Math.max(r_max[i+1], height[i]);
        }
        for(int i=1; i<n-1; i++) {
            ans = ans + Math.min(r_max[i], l_max[i]) - height[i];
        }
        return ans;
    }

    public static int trap3(int[] height) {
        int n = height.length, ans = 0;
        int left = 0, right = n-1;
        int l_max = height[0], r_max = height[n-1];
        while (left < right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);
            if(l_max < r_max) {
                ans = ans + l_max - height[left];
                left++;
            } else {
                ans = ans + r_max - height[right];
                right--;
            }
        }
        return ans;
    }
}
